package org.ring.csr.core;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * @author Ray Ling
 */
public class CheckNodeTree implements Iterable<CheckNodeTree.TreeItem> {
    /**
     * 
     * @author ray
     *
     */
    public static class TreeItem {
	private String path;
	private final CheckNode node;

	public TreeItem(final String path) {
	    this.path = path;
	    this.node = null;
	}

	public TreeItem(final String path, final CheckNode node) {
	    this.path = path;
	    this.node = node;
	}

	public final boolean isTree() {
	    return this.node == null;
	}

	public final boolean isTreeStart() {
	    return isTree() && this.path.charAt(0) != Character.MAX_VALUE;
	}

	public final boolean isTreeEnd() {
	    return isTree() && this.path.charAt(0) == Character.MAX_VALUE;
	}

	public final boolean isItem() {
	    return this.node != null;
	}

	public final String getPath() {
	    return path;
	}

	public final CheckNode getNode() {
	    return node;
	}

	public final String toString() {
	    return path + ":" + node;
	}
    }

    private static final TreeItem TREE_END_ITEM = new TreeItem(
	    String.valueOf(Character.MAX_VALUE), null);

    private final List<TreeItem> tree = new ArrayList<TreeItem>();
    private final String delimiter;

    public CheckNodeTree(final String delimiter) {
	this.delimiter = delimiter;
    }

    public final CheckNodeTree add(final CheckNode node) {
	String path = node.getPath();
	boolean added = false;

	for (int i = 0; i < tree.size() && !added; ++i) {
	    TreeItem item = tree.get(i);
	    String commonPath = findSamePrefix(item.path, path);
	    int delimiterIdx = commonPath.lastIndexOf(delimiter);

	    if (commonPath.length() > 0 && delimiterIdx >= 0
		    && delimiterIdx != item.path.length() - 1) {
		commonPath = commonPath.substring(0, delimiterIdx + 1);

		tree.add(i++, new TreeItem(commonPath));
		path = path.substring(commonPath.length());
		item.path = item.path.substring(commonPath.length());

		int treeIn = item.isTreeStart() ? 1 : 0;
		++i;
		while (treeIn > 0) {
		    if (tree.get(i).isTreeStart()) {
			treeIn++;
		    } else if (tree.get(i).isTreeEnd()) {
			treeIn--;
		    }
		    i++;
		}
		tree.add(i, TREE_END_ITEM);
		i--;
	    } else if (item.isTree()) {
		if (delimiterIdx == item.path.length() - 1) {
		    path = path.substring(item.path.length());
		} else if (path.compareTo(item.path) < 0) {
		    delimiterIdx = path.lastIndexOf(delimiter);
		    if (delimiterIdx > 0) {
			tree.add(
				i++,
				new TreeItem(path
					.substring(0, delimiterIdx + 1)));
			path = path.substring(delimiterIdx + 1);
			tree.add(i, TREE_END_ITEM);
		    }
		    tree.add(i, new TreeItem(path, node));
		    added = true;
		} else {
		    int treeIn = 1;
		    while (treeIn > 0) {
			if (tree.get(++i).isTreeEnd()) {
			    treeIn--;
			} else if (tree.get(i).isTree()) {
			    treeIn++;
			}
		    }
		}
	    } else if (item.isItem()) {
		int cmp = path.compareTo(item.path);
		if (cmp < 0) {
		    delimiterIdx = path.lastIndexOf(delimiter);
		    if (delimiterIdx > 0) {
			tree.add(
				i++,
				new TreeItem(path
					.substring(0, delimiterIdx + 1)));
			path = path.substring(delimiterIdx + 1);
			tree.add(i, TREE_END_ITEM);
		    }
		    tree.add(i, new TreeItem(path, node));
		    added = true;
		    break;
		} else if (cmp == 0) {
		    item.node.combine(node);
		    added = true;
		    break;
		}
	    }
	}
	if (!added) {
	    int delimiterIdx = path.lastIndexOf(delimiter);
	    if (delimiterIdx > 0) {
		tree.add(new TreeItem(path.substring(0, delimiterIdx + 1)));
		path = path.substring(delimiterIdx + 1);
	    }
	    tree.add(new TreeItem(path, node));
	    if (delimiterIdx > 0) {
		tree.add(TREE_END_ITEM);
	    }
	}
	return this;
    }

    public final int countCheckNodes() {
	int size = 0;
	for (TreeItem item : tree) {
	    if (item.isItem()) {
		size++;
	    }
	}
	return size;
    }

    public final int countCheckReports() {
	int size = 0;
	for (TreeItem item : tree) {
	    if (item.isItem()) {
		size += item.node.size();
	    }
	}
	return size;
    }

    private String findSamePrefix(final String a, final String b) {
	int len = 0;
	for (; len < a.length() && len < b.length(); ++len) {
	    if (a.charAt(len) != b.charAt(len)) {
		break;
	    }
	}
	if (len == 0) {
	    return "";
	}
	return a.substring(0, len);
    }

    public final String removeBasePath() {
	String base = null;
	if (tree.get(0).isTreeStart()) {
	    base = tree.get(0).getPath();

	    tree.remove(0);
	    tree.remove(tree.size() - 1);
	}
	return base;
    }

    public final String toString() {
	String str = "CheckNodeTree : \r\n";
	for (TreeItem item : tree) {
	    str += "\t" + item + "\n";
	}
	return str;
    }

    public final Iterator<TreeItem> iterator() {
	return tree.iterator();
    }
}
